The present invention relates to routing, and more specifically, to a routing technique in a Network on Chip (NoC) system.
In recent years, the number of Intellectual Properties (IPs) such as processor cores that can be mounted in one chip has been increasing according to miniaturization of semiconductor processes. The increase in the number of IPs complicates lines connecting IPs and increases the number of lines. Under the circumstance, a Network on Chip (NoC) has attracted attention as a connection network in place of a conventional on chip bus (“Network-on-Chip frontier, Revised Version, August 26, Internet <http:/www.am.ics.keio.ac.jp/members/matutani/papers/matsutani_kyushu2008.ppt>” (Non-patent document 1)).
FIG. 5 corresponds to a part of a slide 8 of Non-patent document 1, and shows network topology of a NoC. In FIG. 5, circles indicate NoC routers. In the following description, a “NoC router” may be simply called a “router”.
The NoC has various topology of tree type, mesh type, and the like. The mesh type is also called a grid type.
As shown in the upper part of FIG. 5, a plurality of routers are connected in layers in the tree type, where each router in an upper layer is directly connected to each router in a layer immediately below. While the tree type of two layers is shown in the example in the upper part of FIG. 5, any number of layers of the tree may be used. In the description of the present invention, that a functional block A is directly connected to a functional block B means a state in which these two functional blocks are connected so as to be able to transmit and receive data with each other without involving a router. Functional blocks are NoC routers or an Intellectual Property (IP). Although a device called a network interface (NI) is actually provided between the IP and the NoC routers, it is described in this specification that the IP and the NoC routers are directly connected for the sake of convenience. Further, the functional block B directly connected to the functional block A is also called “B next to A” or “B adjacent to A”.
As shown in the lower part of FIG. 5, in the mesh type, a plurality of routers are arranged in a lattice shape, and each router is directly connected to other routers on the left, right, up, and down. A hardware configuration of the router of the NoC will be described with reference to the example of the mesh type.
FIG. 6 shows a part of a slide 32 in Non-patent document 1 to which reference symbols are added, and schematically shows a router 10 having five inputs and five outputs. In FIG. 6, “X+”, “X−”, “Y+”, and “Y−” indicate “a right adjacent router of the router 10”, “a left adjacent router of the router 10”, “a router directly below the router 10”, “a router directly above the router 10” (adjacent routers), respectively. In FIG. 6, “CORE” is an IP such as a processor core directly connected to the router 10.
FIG. 7 shows coordinate relations among the router 10 in FIG. 6, CORE, and each of adjacent routers. As shown in FIG. 7, the router 10 is directly connected to CORE and four adjacent routers.
As shown in FIG. 6, the router 10 is connected to CORE and the four adjacent routers by five paths 11, and includes five FIFOs 12, an arbiter (ARBITER in FIG. 6) 14, and an XBAR 16.
The five FIFOs 12 are respectively connected to the five paths 11, and temporarily store packets from the adjacent routers or CORE connected to the paths 11.
The arbiter 14 performs arbitration of output destination of the packet according to the destination of the packet stored in each of the five FIFOs 12. The XBAR 16 has a switching function, and outputs a packet to the output destination according to the arbitration result in the arbiter 14. For example, when the packet for CORE is input from the router of “X+”, the packet is temporarily stored in the FIFO 12 corresponding to the router of “X+”, and thereafter output to CORE. Further, for example, when the packet for an IP (not shown) directly connected to the router of “Y+” is input from the router of “X+”, the packet is temporarily stored in the FIFO 12 corresponding to the router of “X+”, and thereafter output to the router of “Y+”.
Referring to FIG. 8, a configuration of the packet of the NoC will be described using an example of a signal flow when the packet is transmitted from one IP to another IP.
In the example shown in FIG. 8, an IP 20 is a transmission-side IP, which is a master, and an IP 30 is a reception-side IP, which is a slave. A signal transmitted from the IP 20 is received by the IP 30 by way of a Network Interface (NI) 22, a router 24, a router 26, and an NI 28. Note that another router may be provided between the router 24 and the router 26.
The router 24 is directly connected to the IP 20, and the router 26 is directly connected to the IP 30.
The NI 22 packetizes the signal transmitted from the IP 20 to obtain a plurality of flits, and outputs the flits to the router 24.
The top flit of a plurality of flits obtained by the NI 22 is called a head flit, and includes a control signal unit 42 (Control Signal), a source point 44 (Source), and a destination point 46 (Destination). The source point 44 and the destination point 46 are address information that indicates addresses of the transmission source (IP 20, in this example) and the destination (IP 30, in this example), respectively.
Each flit from the second flit is called a body flit, and includes data indicating the content of the signal. The end flit of the body flit is called a tail flit.
The address information may be included in the second flit (the flit next to the head flit) depending on the bus protocol.
In the following description, a plurality of flits from the head flit to the tail flit obtained by packetizing one signal transmitted from the IP of the transmission source is called one “flit group”.
The router 24 sequentially transfers each flit from the NI 22 by time-division multiplexing. More specifically, the router 24 determines the next router from the destination point 46 for each flit group, and sequentially transfers each flit from the head flit to the tail flit to the next router.
Each flit from the router 24 arrives at the router 26 by way of routers provided between the router 24 and the router 26. The router 26 sequentially outputs the flits to the NI 28.
The NI 28 restores a plurality of flits forming one flit group from the router 26 to the signal transmitted or received by the IP to output the restored flits to the IP 30. This restoring processing by the NI 28 is the processing opposite to “packetizing” performed by the NI 22, and hereinafter referred to as “de-packetizing”.
In this manner, transmission from the IP 20 as the master to the IP 30 as the slave is achieved.
A variety of suggestions has been made from various points of view regarding the NoC system.
For example, Japanese Unexamined Patent Application Publication No. 2007-115252 discloses a technique for achieving smooth transfer of data when an advanced extensible interface (AXI) which is an interface protocol of IP is applied to the NoC. Description will be made with reference to FIG. 9.
FIG. 9 corresponds to FIG. 2 of Japanese Unexamined Patent Application Publication No. 2007-115252 while the reference symbols are changed, and shows a configuration of a NoC router 50 to which a technique disclosed in Japanese Unexamined Patent Application Publication No. 2007-115252 is applied.
The NoC router 50 includes a switch 53, an arbiter 51, and an interleaving device 80, switches a plurality of pieces of data (flits) transferred from a plurality of AXI masters (IPs), and transmits the plurality of pieces of data (flits) to an AXI slave 70 (IP) through an NI 60.
The arbiter 51 determines the switching order for passing data received at the switch 53. The switch 53 switches the received data according to the switching order determined by the arbiter 51 to transfer the data to the interleaving device 80 one by one. Although not shown in FIG. 9, the switch 53 is considered to have the similar functions as the plurality of FIFOs 12 and the XBAR 16 in FIG. 6 except that the data is output to the interleaving device 80.
The interleaving device 80 includes a classifier 81, a plurality of buffers 83 respectively provided to the plurality of AXI masters, an output unit 85, and an interleaving manager 87.
The classifier 81 classifies data input through the switch 53, and transfers the data to one of the plurality of buffers 83. The classifier 81 classifies the input data by the AXI master that has transmitted the data, and transfers the data to the buffer 83 corresponding to the AXI master.
The output unit 85 retrieves data from one or more buffers 83 selected according to the control of the interleaving manager 87, and outputs the retrieved data so as to be interleaved.
The interleaving manager 87 receives information on the interleaving acceptance capability from the AXI slave 70, and controls the output unit 85 to interleave and provide as many data as corresponding to the interleaving acceptance capability to the AXI slave 70.
The NI 60 de-packetizes data (interleaved data) output from the output unit 85 and outputs this data to the AXI slave 70.